package com.mlh.dp.背包问题.完全背包;

/**
 * @author 缪林辉
 * @date 2024/4/20 10:44
 * @DESCRIPTION
 */
// 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
// 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
// 假设每一种面额的硬币有无限个。
// 题目数据保证结果符合 32 位带符号整数。
// 输入：amount = 5, coins = [1, 2, 5]
// 输出：4
// 解释：有四种方式可以凑成总金额：
// 5=5
// 5=2+2+1
// 5=2+1+1+1
// 5=1+1+1+1+1
public class 零钱兑换2 {
    public int method1(int amount, int[] coins) {
        int[] dp=new int[amount+1];
        dp[0]=1;//初始化
        //滚动数组
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <=amount; j++) {
                dp[j]= dp[j]+dp[j-coins[i]];//状态推到
            }
        }
        return dp[amount];
    }

    public int practice(int amount, int[] coins){
        int[]dp=new int[amount+1];
        dp[0]=1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <=amount ; j++) {
                dp[j]+=dp[j-coins[i]];
            }
        }
        return dp[amount];
    }

    //调换遍历顺序  先遍历容量 再遍历硬币
    public int practice2(int amount, int[] coins){
        int[]dp=new int[amount+1];
        dp[0]=1;
        for (int i = 1; i <=amount; i++) {
            for (int j = 0; j <coins.length ; j++) {
                if(coins[j]<=i){//硬币大小要小于等于amount
                    dp[i]+=dp[i-coins[j]];
                }
            }
        }
        return dp[amount];
    }
}
